{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 注意！请根据提示操作！\n",
    "\n",
    "如果当页面加载完成，你还是看到了这条提示\n",
    "\n",
    "那么你的notebook并未被信任，导致代码无法正常运行\n",
    "\n",
    "点击右上角的`不可信`，将本notebook列入可信列表，即可正常运行。\n",
    "\n",
    "![可信按钮](./mgr/trust.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 递归\n",
    "\n",
    "递归经常用斐波那契数来说明。\n",
    "\n",
    "斐波那契数，指的是如下的数列：\n",
    "\n",
    "1 1 2 3 5 8 13 21 34 ...\n",
    "\n",
    "除了开始的两个1，其余后面的数字都是其前面两个数字的和。\n",
    "\n",
    "输入一个数字n，请求出第n个斐波那契数，如果用传统的代码，可以写成如下形式："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = int(input())\n",
    "result1 = 1  # 保存第一个结果\n",
    "result2 = 1  # 保存第二个结果，也就是最终输出的数\n",
    "for i in range(1, n + 1):\n",
    "    if i <= 2: continue\n",
    "    result1, result2 = result2, result1 + result2\n",
    "print(result2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果使用递归，可以用如下方法实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = int(input())\n",
    "\n",
    "def f(n):\n",
    "    if n <= 2:\n",
    "        return 1\n",
    "    return f(n - 2) + f(n - 1)  # 函数自身调用自身\n",
    "\n",
    "print(f(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "仔细观察代码，会发现递归其实就是自己调用自己本身，有点类似数学归纳法的味道，也很符合一个故事：\n",
    "\n",
    "```\n",
    "从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，故事讲的是，从前有座山...。\n",
    "```\n",
    "\n",
    "在某些算法中利用递归会让逻辑变得非常清晰，代码也很优美。\n",
    "\n",
    "但是递归的开销其实比较大，需酌情使用。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<hr>\n",
       "<link rel=\"stylesheet\" href=\"//cdn.bootcss.com/mdui/0.4.3/css/mdui.min.css\">\n",
       "<script src=\"./mgr/submit.js\"></script>\n",
       "<script src=\"./mgr/hide.js\"></script>\n",
       "<div class=\"mdui-container-fluid\">\n",
       "    <div class=\"mdui-col-xs-3\">\n",
       "        <button class=\"mdui-btn mdui-btn-raised mdui-ripple mdui-color-blue-grey-500\" onclick=\"next_page(-1)\">上一章</button>\n",
       "    </div>\n",
       "    <div class=\"mdui-col-xs-3\">\n",
       "        <button class=\"mdui-btn mdui-btn-raised mdui-ripple mdui-color-blue-grey-700\" onclick=\"window.open('/tree')\">目录</button>\n",
       "    </div>\n",
       "    <div class=\"mdui-col-xs-3\">\n",
       "        <button class=\"mdui-btn mdui-btn-raised mdui-ripple mdui-color-blue-grey-900\" onclick=\"next_page(1)\">下一章</button>\n",
       "    </div>\n",
       "</div>\n",
       "<div id=\"html_output\">\n",
       "</div>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%html\n",
    "<hr>\n",
    "<link rel=\"stylesheet\" href=\"//cdn.bootcss.com/mdui/0.4.3/css/mdui.min.css\">\n",
    "<script src=\"./mgr/submit.js\"></script>\n",
    "<script src=\"./mgr/hide.js\"></script>\n",
    "<div class=\"mdui-container-fluid\">\n",
    "    <div class=\"mdui-col-xs-3\">\n",
    "        <button class=\"mdui-btn mdui-btn-raised mdui-ripple mdui-color-blue-grey-500\" onclick=\"next_page(-1)\">上一章</button>\n",
    "    </div>\n",
    "    <div class=\"mdui-col-xs-3\">\n",
    "        <button class=\"mdui-btn mdui-btn-raised mdui-ripple mdui-color-blue-grey-700\" onclick=\"window.open('/tree')\">目录</button>\n",
    "    </div>\n",
    "    <div class=\"mdui-col-xs-3\">\n",
    "        <button class=\"mdui-btn mdui-btn-raised mdui-ripple mdui-color-blue-grey-900\" onclick=\"next_page(1)\">下一章</button>\n",
    "    </div>\n",
    "</div>\n",
    "<div id=\"html_output\">\n",
    "</div>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
